// 读完本文，你不仅学会了算法套路，还可以顺便去 LeetCode 上拿下如下题目：
//
// [509.斐波那契数](https://leetcode-cn.com/problems/fibonacci-number)
//
// [322.零钱兑换](https://leetcode-cn.com/problems/coin-change)

let fib = function (n) {
    if (n === 1 || n === 2) {
        return 1;
    }

    return fib(n - 1) + fib(n - 2);
};


fib = function (n) {
    if (n < 1) return 0;

    // 备忘录全初始化为 0
    let memo = new Array(n + 1);
    memo.fill(0, 0, n + 1);
    // 进行带备忘录的递归
    return helper(memo, n);
}

let helper = function (memo, n) {
    // base case
    if (n === 1 || n === 2) return 1;
    // 已经计算过
    if (memo[n] !== 0) return memo[n];

    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}

fib = function (n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    let dp = new Array(n + 1);
    dp.fill(0, 0, n + 1);
    // base case
    dp[1] = dp[2] = 1;
    for (let i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}


fib = function (n) {
    if (n === 2 || n === 1)
        return 1;
    let prev = 1, curr = 1;
    for (let i = 3; i <= n; i++) {
        let sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}


var coinChange = function (coins, amount) {
    this.dp = function (n) {
        // base case
        if (n === 0) {
            return 0
        }
        if (n < 0) {
            return -1
        }

        // 求最小值，所以初始化为正无穷
        let res = Infinity
        for (let coin of coins) {
            // 计算子问题
            let subproblem = dp(n - coin)

            // 子问题无解，跳过
            if (subproblem === -1)
                continue;

            // 个数为 1 + 子问题的解, 1为选择来当前coin金额的硬币
            res = Math.min(res, 1 + subproblem)
        }
        return res !== Infinity ? res : -1;
    }
    return dp(amount)
};


var coinChange = function (coins, amount) {
    // 备忘录
    let memo = {};

    this.dp = function (n) {
        // 查备忘录，避免重复计算
        if (memo[n] !== undefined) {
            return memo[n];
        }

        // base case
        if (n === 0) {
            return 0
        }
        if (n < 0) {
            return -1
        }

        // 求最小值，所以初始化为正无穷 或者是amount+1
        let res = Infinity;
        for (let coin of coins) {
            const subProblem = dp(n - coin)
            // 子问题无解，跳过
            if (subProblem === -1)
                continue;

            // 个数为 1 + 子问题的解
            res = Math.min(res, 1 + subProblem)
        }
        // 记录在备忘录里
        memo[n] = res === Infinity ? -1 : res
        return memo[n];
    }

    return dp(amount)
};

console.log(coinChange([1, 2, 5], 11))


var coinChange = function (coins, amount) {
    let memo = {};

    this.dp = function (amount) {
        if (memo[amount] !== undefined) {
            return memo[amount];
        }
        if (amount === 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }

        let result = Infinity;
        for (let coin of coins) {
            // 计算子问题
            const subResult = dp(amount - coin);
            // 子问题无解
            if (subResult === -1) {
                continue;
            }
            // 个数为 1 + 子问题的解
            result = Math.min(result, 1 + subResult);
        }

        // 备忘录
        memo[amount] = result == Infinity ? -1 : result;
        return memo[amount];
    };

    return dp(amount);
}


console.log(coinChange([1, 2, 5], 11))

var coinChange = function (coins, amount) {
    // 数组大小为 amount + 1，初始值也为 amount + 1
    let dp = new Array(amount + 1);
    dp.fill(amount + 1, 0, amount + 1);

    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (let i = 0; i < dp.length; i++) {
        // 内层 for 循环在求所有选择的最小值
        for (let coin of coins) {
            // 子问题无解，跳过
            if (i - coin < 0) continue;
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] === amount + 1) ? -1 : dp[amount];
}
console.log(coinChange([1, 2, 5], 11))
